class Solution {
public:
    TreeNode* change(TreeNode* root,int val,int depth){
        if(!root) return NULL;
        
        if(depth == 2){
            TreeNode* node1 = new TreeNode(val);
            node1->left = root->left;
            root->left = node1;
            
            TreeNode* node2 = new TreeNode(val);
            node2->right = root->right;
            root->right = node2;
            
            return root;
        }
        
        root->left = change(root->left,val,depth-1);
        root->right = change(root->right,val,depth-1);
        
        return root;
    
    }
                                        
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(depth <= 0) return root;
        if(depth == 1){
            TreeNode* node = new TreeNode(val);
            node->left = root;
            return node;
        }
        
        return change(root,val,depth);
    }
};

